
import java.util.*;

public class Solution {
    public int numDecodings(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[] dp = new int[n];
        if(arr[0] != '0'){
            dp[0] = 1;
        }
        if(n == 1){
            return dp[0];
        }
        if(arr[1] >= '1' && arr[1] <= '9'){
            dp[1]++;
        }
        String tmp = s.substring(0,2);
        int num = Integer.parseInt(tmp);
        if(num >= 10 && num <= 26){
            dp[1]++;
        }

        for(int i = 2; i < n; i++){
            if(arr[i] >= '1' && arr[i] <= '9'){
                dp[i] = dp[i - 1];
            }
            tmp = s.substring(i - 1, i + 1);
            num = Integer.parseInt(tmp);
            if(num >= 10 && num <= 26){
                dp[i] += dp[i - 2];
            }
        }
        for(Integer number : dp){
            if(number == 0){
                return 0;
            }
        }
        return dp[n - 1];
    }

    public void run() { // 样列放在这
    }

    public static void main(String[] args) {
        new Solution().run();
    }

    <T> void pr(T t) {
        System.out.println(t);
    }

    void tr(Object... o) { // 调试函数
        System.out.println(Arrays.deepToString(o));
    }
}

